Flash memory, which is a type of non-volatile computer readable memory that can be electrically programmed and erased, is used to store data persistently for embedded systems, personal computers and enterprise systems. A flash file-system accesses and stores data on flash memory and provides the operating system (OS) with file-system interfaces to read and to write to flash memory. For read and write operations, the flash file-system sends commands and data to the flash controller, which retrieves or stores the data into the flash memory. Thus, a flash file-system interacts with the flash controller, which interfaces with the flash memory, which can be implemented in a flash memory device. Flash memory is typically read and written in pages with each page having a size of 2K or 4K bytes. In addition, each page is associated with a ‘spare area’ that has a size of 32 or 64 bytes. The standard use for the spare area is to store information such as ECC (Error Correction Codes), Logical Page numbers and Erase counts, among other information. This spare area and the actual data area are read and are written together from flash memory by the flash controller (and by flash file-system).
File-systems make use of access pattern information. For example, sequential/strided access patterns may be detected by a monitoring unit of the file-system and used for optimizations such as pre-fetching. However, non-linear/non-strided access patterns are typically not captured. Capturing such information requires additional memory and extra storage space. For non-linear/non-strided patterns, making the captured access information persistent is very useful as this does not require the re-construction of information every time after a system re-start. In addition, multi-stream information is usually not captured by the file-systems. This may require maintaining multiple ‘possible next accesses’ for a particular access, resulting in larger memory and storage overhead.
Therefore, both flash file-systems and traditional file-systems do not provide ways to capture non-linear/non-strided patterns of memory accesses or multiple streams of memory accesses. Having persistent, multiple stream access information for non-linear/non-strided patterns is not only useful for the flash file-system for optimizations such as pre-fetching but can also be used by other tools for pattern analysis and mining.